#include <iostream>
#include<fstream>
#include<vector>
#include<string>
#include<list>
using namespace std;

class SrcNode
{
	public:
    list <SrcNode *> children;
	int matched_rule;
	int stride_num;
		SrcNode()
		{
			
		}
	 	void printTree()
  		{
  			
   	}
};

class Rule
{
    public:
	//rule contains dst / src and rule number as of now
	int rule_num;
	string dest;
	string src;
		Rule(int rule_no, string dst, string source)
		{
			rule_num = rule_no;
			dest = dst;
			src = source;
		}
	  void print()
      {
         cout<<rule_num<<" "<<dest<<" "<<src<<"\n";
      }
};

vector<Rule *> rules;
void printRules()
{
    for(int i=0;i<rules.size();i++)
    {
        rules[i]->print();
    }
}
void readInputFromFile()
{
	//read into rules
	 string str;
   int rule_no = 0;
   ifstream fp("rules.txt");
   if (fp.is_open())
   {
      while (fp.good())
      {
         getline(fp, str);
         string dest = str.substr(0, str.find(' '));
         string src = str.substr(str.find(' ') + 1, str.length());
         rule_no++;
         Rule *rule = new Rule(rule_no, dest, src);
         rules.push_back(rule);
      }
   }
   else
   {
      cout<<"Error in opening file";
   }
   fp.close();
}

class DestNode
{
	public:
        SrcNode * ptr_to_src;
        list<int> list_of_rules;
        DestNode * left;
        DestNode * right;
        DestNode * parent;
        bool has_rules;
        string pattern;       
    DestNode(DestNode * parent,string patt)
    {
    	ptr_to_src = NULL;
        pattern=patt;
       	left = NULL;
   	    right = NULL;
    	has_rules = false;
   }
   void  buildTree(Rule r)
   {
   	//add 
   }
   void buildSrcTree()
   {   	
   	//if a destination node contains has_rules as true, construct a source tree for that dest and so on.	
		//should be called with root   
	 	if(has_rules)
	 	{
	 		ptr_to_src = new SrcNode();
	 		//call our adaptive set pruning trie function 
	 	}
	 	if(this->left)
	 		left->buildSrcTree();
	 	if(this->right)
	 		right->buildSrcTree();
   }
   void printTree()
   {
     cout<<pattern<<endl;
   	 if(left)
         left->printTree();
     if(right)
         right->printTree();
   }
   void adaptiveTreeBuild()
 	{
 	}
   DestNode * merge_rule_set()
   {
   	//copy the list_of_rules from parent to child and recurse.
   }
};
//takes all rules and builds the trie
 
DestNode * createDestTree()
{
	DestNode * root = new DestNode(NULL,string(""));//rootukku ethu parent-u
	DestNode * current = root;
		for(int i=0;i<rules.size();i++)
		{
			for(int j=0;j<rules[i]->dest.length();j++)
			{
				char currentchar  = rules[i]->dest[j];
				if(currentchar=='0')
				{
					if(current->left==NULL)
					{
						current->left = new DestNode(current,current->pattern+"0");
					}
					current = current->left;
					
				}
				else if(currentchar=='1')
				{
				   if(current->right==NULL)
					{
						current->right = new DestNode(current,current->pattern+"1");
					}
					current = current->right;
				}
				else if(currentchar=='*')
				{
					current->has_rules = true;
					current->list_of_rules.push_back(i+1);//rule numbers are from onnu
				}
			}	
		}
		return root;
}
int main()
{
	readInputFromFile();
    //printRules();
    
	DestNode * root = createDestTree();
	
    root->printTree();
	return 0;
}
